package org.gpf;

import java.util.Arrays;

/**
 * 减治
 * @author gaopengfei
 * @date 2015-4-22 下午6:32:28
 */
public class DecreaseConquer {

	/**
	 * 倒置数组元素
	 * @param arr 需要倒置的数组
	 * @param start 需要倒置数组的起始下标
	 * @param end 需要倒置数组的结束下标
	 */
//	private static void reverse(int[] arr, int start, int end) {
//
//		// 问题规模到的奇偶性不变，需要2个递归基
//		if (start < end) {
//			int temp = arr[start];
//			arr[start] = arr[end];
//			arr[end] = temp;
//			reverse(arr, start + 1, end - 1);
//		}
//		/*
//		 * 这其实是if的隐含条件，实际上就是我们所需要的递归基
//			else {
//				return;
//			}
//		*/
//	}
	
	/**
	 * 数组倒置的迭代实现
	 * @param arr 需要倒置的数组
	 * @param start 数组的起始下标
	 * @param end 数组的结束下标
	 */
	private static void reverse(int[] arr,int start,int end){
		
		if (start < end) {
			int temp = arr[start];
			arr[start] = arr[end];
			arr[end] = temp;
			start++;
			end--;
		}
		
	}
	
	/**
	 * 迭代的方式，依次取出数组中的每一个元素，累加之
	 * 复杂度为O(n)
	 */
	private static int sum(int[] arr,int len){
		
		int sum = 0;

		for (int i = 0; i < len; i++) {
			sum += arr[i];
		}
		return sum;
		
	}

	/**
	 * 数组求和 线性递归
	 * arr 数组
	 * len 数组长度
	 * 复杂度为O(n)
	 */
	private static int getSum(int[] arr,int len){
		
		return len < 1 ? 0 : getSum(arr, len - 1) + arr[len - 1];
	}
	
	public static void main(String[] args) {
		
		int[] arr = {1,2,3,4,5,6,7,8,9,10};
		reverse(arr, 0, arr.length-1);
		System.out.println(Arrays.toString(arr));
	}

}
